{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 基本概念"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算。用关键字标识一个数据元素，查找时根据给定的某个值，在表中确定一个关键字的值等于给定值的记录或数据元素。在计算机中进行查找的方法是根据表中的记录的组织结构确定的。<sup>[Re-百度百科](https://baike.baidu.com/item/查找算法/12597242?fr=aladdin)\n",
    "\n",
    "查找算法分类：  \n",
    "1）静态查找和动态查找；注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。  \n",
    "2）无序查找和有序查找。 \n",
    "- 无序查找：被查找数列有序无序均可；  \n",
    "- 有序查找：被查找数列必须为有序数列。  \n",
    "\n",
    "平均查找长度（Average Search Length，ASL）：需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。  \n",
    "对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci的和。  \n",
    "- Pi：查找表中第i个数据元素的概率。  \n",
    "- Ci：找到第i个数据元素时已经比较过的次数。  \n",
    "\n",
    "\n",
    "目前常见的7大查找算法包括：  \n",
    "    1. 顺序查找  \n",
    "    2. 二分查找  \n",
    "        - 3. 插值查找  \n",
    "        - 4. 斐波那契查找  \n",
    "    5. 分块查找   \n",
    "    6. 哈希查找(散列查找)     \n",
    "    7. 树表查找(树型结构，后续章节介绍)   \n",
    "   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 顺序查找（Sequential Search）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "顺序查找的过程(如下图)：从表中第一个（ 或最后一个）开始，逐个记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果知道最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。  \n",
    "![顺序查找]()\n",
    "- 说明：顺序查找适合于存储结构为顺序存储或链接存储的线性表。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-07-30T05:04:40.015428Z",
     "iopub.status.busy": "2020-07-30T05:04:40.014170Z",
     "iopub.status.idle": "2020-07-30T05:04:40.025771Z",
     "shell.execute_reply": "2020-07-30T05:04:40.024818Z",
     "shell.execute_reply.started": "2020-07-30T05:04:40.015167Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(-1, 9)\n",
      "(7, 8)\n",
      "(0, 1)\n"
     ]
    }
   ],
   "source": [
    "def seq_search(list,tar):\n",
    "    length = len(list)\n",
    "    pos = 0\n",
    "    times = 0 # 统计循环了几次\n",
    "    while pos < length:\n",
    "        times += 1\n",
    "        if list[pos] == tar:\n",
    "            return pos, times\n",
    "        else:\n",
    "            pos += 1\n",
    "    return -1, times\n",
    "\n",
    "testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]\n",
    "print(seq_search(testlist, 3))\n",
    "print(seq_search(testlist, 13))\n",
    "print(seq_search(testlist, 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于无序列表的查找，顺序查找的比对如下：  \n",
    "\n",
    "<center>顺序查找在无序列表中的表现</center>\n",
    "    \n",
    "|Case |Best Case| Worst Case| Average Case|\n",
    "|--|:--:|:--:|:--:|\n",
    "|item is present| 1 |𝑛 |𝑛/2|\n",
    "|item is not present| 𝑛| 𝑛 |𝑛|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "当一个表是按照一个递增的顺序构建的时候，如果判断一个元素是否在列表内，查找方法与上述一致，但判断不存在则比无序表更有优势，当查找到比目标数字更大的数字时仍未查到目标数字，则说明目标数字不在列表内，如下图所示，若查找50是否在表内，则仅需要查找到54即可判断除50不在表内。  \n",
    "\n",
    "\n",
    "![顺序查找2]()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-07-30T05:04:42.299592Z",
     "iopub.status.busy": "2020-07-30T05:04:42.298602Z",
     "iopub.status.idle": "2020-07-30T05:04:42.314886Z",
     "shell.execute_reply": "2020-07-30T05:04:42.313396Z",
     "shell.execute_reply.started": "2020-07-30T05:04:42.299592Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(-1, 4)\n",
      "(4, 5)\n",
      "(1, 2)\n"
     ]
    }
   ],
   "source": [
    "# 代码实现\n",
    "def ord_seq_search(list,tar):\n",
    "    length = len(list)\n",
    "    pos = 0\n",
    "    times = 0\n",
    "    while pos < length:\n",
    "        times += 1\n",
    "        if list[pos] == tar:\n",
    "            return pos, times\n",
    "        elif list[pos] > tar:\n",
    "            return -1, times\n",
    "        else:\n",
    "            pos += 1\n",
    "    return -1, times\n",
    "\n",
    "order_list = [0, 1, 2, 8, 13, 17, 19, 32, 42]\n",
    "print(ord_seq_search(order_list,3))\n",
    "print(ord_seq_search(order_list,13))\n",
    "print(ord_seq_search(order_list,1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "下表总结了以上所说的这些可能的结果。注意，当我们可以发现项不在列表时，最好结果只需要看一个数据项。平均一下，通过遍历n/2的数据项，我们将知道目标项是否在列表中。  \n",
    "\n",
    "<center>顺序查找在有序列表中的表现</center>\n",
    "    \n",
    "|Case |Best Case| Worst Case| Average Case|\n",
    "|--|:--:|:--:|:--:|\n",
    "|item is present| 1 |𝑛 |𝑛/2|\n",
    "|item is not present| 1| 𝑛 |𝑛/2|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 二分查找\n",
    "二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法,二分搜索的复杂度是O(log(n))。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-07-30T10:30:41.021120Z",
     "iopub.status.busy": "2020-07-30T10:30:41.021120Z",
     "iopub.status.idle": "2020-07-30T10:30:41.045856Z",
     "shell.execute_reply": "2020-07-30T10:30:41.043858Z",
     "shell.execute_reply.started": "2020-07-30T10:30:41.021120Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(-1, 4)\n",
      "(4, 1)\n",
      "(1, 2)\n",
      "(0, 3)\n"
     ]
    }
   ],
   "source": [
    "def binary_search(list,tar):\n",
    "    low = 0\n",
    "    high = len(list)-1\n",
    "    times = 0\n",
    "    while low <= high:\n",
    "        times += 1\n",
    "        mid = (low+high)//2\n",
    "#         print(mid)\n",
    "        if tar == list[mid]:\n",
    "            return mid, times\n",
    "        elif tar > list[mid]:\n",
    "            low = mid + 1\n",
    "        else:\n",
    "            high = mid - 1\n",
    "    return -1, times\n",
    "            \n",
    "order_list = [0, 1, 2, 8, 13, 17, 19, 32, 42]\n",
    "print(binary_search(order_list,3))\n",
    "print(binary_search(order_list,13))\n",
    "print(binary_search(order_list,1))\n",
    "print(binary_search(order_list,0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 变种1：旋转有序数组的二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "什么是旋转有序数组?\n",
    "答：假设有个有序数组在某个位置旋转，得到新的数组，即为旋转有序数组。例如数组{6,7,8,1,2,3,4,5}便是经数组{1,2,3,4,5,6,7,8}旋转而来的旋转有序数组，其中我们将1称为旋转点(旋转序列中的最小元素)。  \n",
    "旋转有序数组不再满足二分查找的使用条件。\n",
    "\n",
    "**分析**\n",
    "可以参考[这篇文章](https://blog.csdn.net/bjweimengshu/article/details/90826510)，讲的很好,当对旋转有序数组使用二分查找时，有以下四种情况：  \n",
    "\n",
    "A：旋转点在中位数的右侧，例如{3,4,5,<font color=red>6</font>,7,8,1,2}：  \n",
    "- 查找目标在中位数的左侧时，最左侧元素 <= 查找目标 < 中位数；\n",
    "- 查找目标在中位数的右侧时，！（最左侧元素 <= 查找目标 < 中位数）  \n",
    "\n",
    "B：旋转点在中位数的左侧，例如{7,8,1,<font color=red>2</font>,3,4,5,6}：\n",
    "- 查找目标在中位数的右侧时，中位数 < 查找目标 <= 最右侧元素 \n",
    "- 查找目标在中位数的左侧时，！（中位数 < 查找目标 <= 最右侧元素） "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "加上中位数等于查找目标的情况，梳理代码逻辑如下：  \n",
    "![旋转列表二分逻辑]()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-03T05:16:31.301670Z",
     "iopub.status.busy": "2020-08-03T05:16:31.300671Z",
     "iopub.status.idle": "2020-08-03T05:16:31.320338Z",
     "shell.execute_reply": "2020-08-03T05:16:31.317226Z",
     "shell.execute_reply.started": "2020-08-03T05:16:31.301670Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(-1, 3)\n",
      "(3, 4)\n",
      "(7, 3)\n",
      "(8, 4)\n",
      "(2, 3)\n"
     ]
    }
   ],
   "source": [
    "# 根据以上四种情况，梳理代码如下\n",
    "def ro_binary_search(list_s, tar):\n",
    "    low = 0\n",
    "    high = len(list_s)-1\n",
    "    times = 0\n",
    "    while low<=high:\n",
    "        times += 1\n",
    "        mid = (low+high)//2\n",
    "        if tar == list_s[mid]:\n",
    "            return mid,times\n",
    "        # 旋转点在中点右侧\n",
    "        elif list_s[mid] >= list_s[low]: \n",
    "            if tar>=list_s[low] and tar<list_s[mid]: # 目标在中点左侧\n",
    "                high = mid -1\n",
    "            else:\n",
    "                low = mid + 1\n",
    "        # 旋转点在中点左侧\n",
    "        else: \n",
    "            if tar<=list_s[high] and tar>list_s[mid]:\n",
    "                low = mid +1\n",
    "            else:\n",
    "                high = mid -1           \n",
    "    return -1, times\n",
    "            \n",
    "print(ro_binary_search([ 19, 32, 42, 0, 1, 2, 8, 13, 17],3))\n",
    "print(ro_binary_search([ 19, 32, 42, 0, 1, 2, 8, 13, 17],0))\n",
    "print(ro_binary_search([ 19, 32, 42, 0, 1, 2, 8, 13, 17],13))\n",
    "print(ro_binary_search([ 19, 32, 42, 0, 1, 2, 8, 13, 17],17))\n",
    "print(ro_binary_search([ 2, 8, 13, 17, 19, 32, 42, 0, 1],13))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 变种2：插值查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "插值查找，有序表的一种查找方式。插值查找是根据查找关键字与查找表中最大最小记录关键字比较后的查找方法,插值查找基于二分查找，将查找点的选择改进为自适应选择，提高查找效率,比二分查找多了一项key列表，其中值表达式为：  \n",
    "$$mid = low+\\frac{key-a[low]}{a[high]-a[low]}(high-low)$$  \n",
    "其中，$key$为目标值；$a$为待查列表；  \n",
    "注意：对于极端分布的列表，插值查找效率较低，例如：a={0,1,2,100,102,1000,10000}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-03T06:26:38.948659Z",
     "iopub.status.busy": "2020-08-03T06:26:38.947662Z",
     "iopub.status.idle": "2020-08-03T06:26:38.962197Z",
     "shell.execute_reply": "2020-08-03T06:26:38.959203Z",
     "shell.execute_reply.started": "2020-08-03T06:26:38.948659Z"
    }
   },
   "outputs": [],
   "source": [
    "# 二分查找\n",
    "def binary_search(list_s,tar):\n",
    "    low = 0\n",
    "    high = len(list_s)-1\n",
    "    times = 0\n",
    "    while low <= high:\n",
    "        times += 1\n",
    "        mid = (low+high)//2\n",
    "        print('二分',low,mid,high)\n",
    "#         print(mid)\n",
    "        if tar == list_s[mid]:\n",
    "            return mid, times\n",
    "        elif tar > list_s[mid]:\n",
    "            low = mid + 1\n",
    "        else:\n",
    "            high = mid - 1\n",
    "    return -1, times\n",
    "\n",
    "# 在二分查找的基础上修改的插值查找\n",
    "def binary_search_auto(list_s,tar):\n",
    "    low = 0\n",
    "    high = len(list_s)-1\n",
    "    times = 0\n",
    "    while low <= high:\n",
    "        times += 1\n",
    "        mid = low + int((high-low)*(tar-list_s[low])/(list_s[high]-list_s[low]))\n",
    "        print('插值',low,mid,high)\n",
    "#         print(low<=high)\n",
    "#         print(mid)\n",
    "        if tar == list_s[mid]:\n",
    "            return mid, times\n",
    "        elif tar > list_s[mid]:\n",
    "            low = mid + 1\n",
    "        else:\n",
    "            high = mid - 1\n",
    "    return -1, times"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以看出插值查找在查找某些值时结果更快，有些则比较慢"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-03T06:26:41.310954Z",
     "iopub.status.busy": "2020-08-03T06:26:41.310954Z",
     "iopub.status.idle": "2020-08-03T06:26:41.321965Z",
     "shell.execute_reply": "2020-08-03T06:26:41.320955Z",
     "shell.execute_reply.started": "2020-08-03T06:26:41.310954Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "二分 0 4 8\n",
      "二分 0 1 3\n",
      "二分 2 2 3\n",
      "二分 3 3 3\n",
      "插值 0 0 8\n",
      "插值 1 1 8\n",
      "插值 2 2 8\n",
      "插值 3 3 8\n",
      "(-1, 4) (-1, 4)\n",
      "二分 0 4 8\n",
      "插值 0 2 8\n",
      "插值 3 3 8\n",
      "插值 4 4 8\n",
      "(4, 1) (4, 3)\n",
      "二分 0 4 8\n",
      "二分 5 6 8\n",
      "二分 7 7 8\n",
      "插值 0 6 8\n",
      "插值 7 7 8\n",
      "(7, 3) (7, 2)\n",
      "二分 0 4 8\n",
      "二分 0 1 3\n",
      "二分 0 0 0\n",
      "插值 0 0 8\n",
      "(0, 3) (0, 1)\n"
     ]
    }
   ],
   "source": [
    "order_list = [0, 1, 2, 8, 13, 17, 19, 32, 42]\n",
    "print(binary_search(order_list,3),binary_search_auto(order_list,3))\n",
    "print(binary_search(order_list,13),binary_search_auto(order_list,13))\n",
    "print(binary_search(order_list,32),binary_search_auto(order_list,32))\n",
    "print(binary_search(order_list,0),binary_search_auto(order_list,0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-03T06:26:45.002723Z",
     "iopub.status.busy": "2020-08-03T06:26:45.002723Z",
     "iopub.status.idle": "2020-08-03T06:26:45.019911Z",
     "shell.execute_reply": "2020-08-03T06:26:45.018913Z",
     "shell.execute_reply.started": "2020-08-03T06:26:45.002723Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "二分 0 4 8\n",
      "插值 0 4 8\n",
      "(4, 1) (4, 1)\n",
      "二分 0 4 8\n",
      "二分 5 6 8\n",
      "二分 7 7 8\n",
      "二分 8 8 8\n",
      "插值 0 8 8\n",
      "(8, 4) (8, 1)\n",
      "二分 0 4 8\n",
      "二分 0 1 3\n",
      "二分 0 0 0\n",
      "插值 0 0 8\n",
      "(0, 3) (0, 1)\n",
      "二分 0 4 8\n",
      "二分 0 1 3\n",
      "插值 0 0 8\n",
      "插值 1 1 8\n",
      "(1, 2) (1, 2)\n"
     ]
    }
   ],
   "source": [
    "order_list = [0, 1, 2, 8, 13, 17, 19, 20, 21]\n",
    "# \n",
    "print(binary_search(order_list,13),binary_search_auto(order_list,13))\n",
    "print(binary_search(order_list,21),binary_search_auto(order_list,21))\n",
    "print(binary_search(order_list,0),binary_search_auto(order_list,0))\n",
    "print(binary_search(order_list,1),binary_search_auto(order_list,1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-03T06:26:54.769917Z",
     "iopub.status.busy": "2020-08-03T06:26:54.768899Z",
     "iopub.status.idle": "2020-08-03T06:26:54.776298Z",
     "shell.execute_reply": "2020-08-03T06:26:54.774906Z",
     "shell.execute_reply.started": "2020-08-03T06:26:54.769917Z"
    }
   },
   "outputs": [],
   "source": [
    "# TODO 这个数组会查找不到3s时不会退出，无限循环,\n",
    "# 经分析原因在mid = low + int((high-low)*(tar-list_s[low])/(list_s[high]-list_s[low]))这句上\n",
    "# 当low =3,high=8  tar =3时，计算结果永远是3，2，8\n",
    "print(binary_search(order_list,3),binary_search_auto(order_list,3))，"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 变种3：斐波那契查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "斐波那契搜索就是在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于略大于查找表中元素个数的数F[n]，将原查找表扩展为长度为F[n](如果要补充元素，则补充重复最后一个元素，直到满足F[n]个元素)，完成后进行斐波那契分割，即F[n]个元素分割为前半部分F[n-1]个元素，后半部分F[n-2]个元素，找出要查找的元素在那一部分并递归，直到找到。  \n",
    "\n",
    "斐波那契思想与二分法相类似，不过中间点不再是中点，而变成了黄金分割点的附近，表达式为：$$mid=low+F(k-1)-1$$\n",
    "- 其中：$F$为斐波那契数列；$k$代表斐波那契数列的第k个元素  \n",
    "- 由斐波那契数列$F[k]=F[k-1]+F[k-2]$的特点，可以得到$F[k]-1=(F[k-1]-1)+(F[k-2]-1) + 1$,这个式子说明只要是顺序表的长度为$F[k]-1$,就可以分为($F[k-1]-1$)和($F[k-2]-1$)两段，另外一个1就是\n",
    "mid位置的元素。  \n",
    "- 但是顺序表的长度不一定是恰好等于F[k]-1,所以需要将原来的顺序表的长度增加到F[k]-1,这里的k值仅仅需要恰好使得F[k]-1恰好大于或者等于n,新增位置，都赋值为下标为n-1位置的值就可以了  \n",
    "下图是精髓，注意理解\n",
    "\n",
    "![]()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-03T08:31:04.008156Z",
     "iopub.status.busy": "2020-08-03T08:31:04.006809Z",
     "iopub.status.idle": "2020-08-03T08:31:04.021635Z",
     "shell.execute_reply": "2020-08-03T08:31:04.020638Z",
     "shell.execute_reply.started": "2020-08-03T08:31:04.006809Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "fib数列: [0, 1, 1, 2, 3, 5, 8, 13]\n",
      "list_:  [1, 2, 4, 5, 9, 11, 20, 33, 44, 50, 50, 50]\n",
      "7\n",
      "4\n",
      "6\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "def get_fib(list_len):\n",
    "    a, b = 0, 1\n",
    "    fib = []\n",
    "    while True:\n",
    "        fib.append(a)\n",
    "        if a > list_len:\n",
    "            print('fib数列:', fib)\n",
    "            return fib\n",
    "        else:\n",
    "            a, b = b, a + b\n",
    "\n",
    "\n",
    "def fib_find(find_num, index, list_, fib, k):\n",
    "    split_pos = fib[index-1] - 1\n",
    "    print(split_pos+k)\n",
    "    if find_num == list_[split_pos]:\n",
    "        return split_pos + k\n",
    "    elif len(list_) == 0:\n",
    "        return None\n",
    "    elif find_num < list_[split_pos]:\n",
    "        return fib_find(find_num, index-1, list_[:split_pos+1], fib, k)  # 在左侧时，k = k-1\n",
    "    else:\n",
    "        return fib_find(find_num, index-2, list_[split_pos+1:], fib, k+fib[index-1])# 在右侧时，k = k-2\n",
    "\n",
    "\n",
    "def fib_search_(find_num, list_, fib):\n",
    "    list_len = len(list_)\n",
    "    index, good_len = len(fib)-1, fib[-1]-1\n",
    "    [list_.append(list_[-1]) for i in range(good_len-list_len)] # 将数组补全到F(k)-1\n",
    "    print('list_: ',list_)\n",
    "    final_index = fib_find(find_num, index, list_, fib, 0)\n",
    "    [list_.pop() for i in range(good_len-list_len)]\n",
    "    if final_index > list_len - 1:\n",
    "        return list_len - 1\n",
    "    else:\n",
    "        return final_index\n",
    "\n",
    "\n",
    "def fib_search(find_num, list_):\n",
    "    fib = get_fib(len(list_))\n",
    "    return fib_search_(find_num, list_, fib)\n",
    "\n",
    "\n",
    "\n",
    "list_ = [1, 2, 4, 5, 9, 11, 20, 33, 44, 50]\n",
    "find_num = 20\n",
    "print(fib_search(find_num, list_))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上述代码及以下结论参考了[这里](https://www.meiwen.com.cn/subject/vkmxgttx.html)https://www.meiwen.com.cn/subject/vkmxgttx.html。  \n",
    "根据资料显示，斐波那契查找的平均效率会比折半查找更高。但在 Python 中，根据测试发现，使用斐波那契查找时，列表的 append 和 pop 操作比较消耗时间；除此之外，递归次数也比折半查找要多。\n",
    "总之，在大多数时候，有序线性表查找时直接使用折半查找足以使用。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 分块查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "分块查找是折半查找和顺序查找的一种改进方法，折半查找虽然具有很好的性能，但其前提条件时线性表顺序存储而且按照关键码排序，这一前提条件在结点树很大且表元素动态变化时是难以满足的。而顺序查找可以解决表元素动态变化的要求，但查找效率很低。如果既要保持对线性表的查找具有较快的速度，又要能够满足表元素动态变化的要求，则可采用分块查找的方法。  \n",
    "算法要求序列具有以下特点：\n",
    "- 将n个数据元素\"按块有序\"划分为m块（m ≤ n）。\n",
    "- 每一块中的结点不必有序，但块与块之间必须\"按块有序\"；\n",
    "- 每个块内的的最大元素小于下一块所有元素的任意一个值。\n",
    "![]()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "所以，给定一个待查找的key，在查找这个key值位置时，会先去索引表中利用顺序查找或者二分查找来找出这个key所在块的索引开始位置，然后再根据所在块的索引开始位置开始顺序查找这个key所在的具体位置。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-04T03:01:31.529081Z",
     "iopub.status.busy": "2020-08-04T03:01:31.527918Z",
     "iopub.status.idle": "2020-08-04T03:01:31.565758Z",
     "shell.execute_reply": "2020-08-04T03:01:31.564761Z",
     "shell.execute_reply.started": "2020-08-04T03:01:31.529081Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "merge_list [2, 1, 9, 9, 7, 13, 15, 14, 10, 19, 20, 28, 24, 24, 28, 31, 39, 30, 31, 38, 47, 42, 48, 44, 41]\n",
      "max_list [9, 19, 28, 39, 48]\n",
      "block_num:  2\n",
      "search_list:  [20, 28, 24, 24, 28]\n",
      "顺序搜索未找到\n",
      "-1\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "import timeit\n",
    "# 构建分块数据，下面只是一种呈现形式示，不要局限于这种\n",
    "# 也可以分为不同列表去存储，根据数据特点来确定\n",
    "list5 = [random.randrange(0,10) for i in range(5)] \n",
    "list10 = [random.randrange(10,20) for i in range(5)]\n",
    "list20 = [random.randrange(20,30) for i in range(5)]\n",
    "list30 = [random.randrange(30,40) for i in range(5)]\n",
    "list40 = [random.randrange(40,50) for i in range(5)]\n",
    "merge_list = list5+list10+list20+list30+list40\n",
    "print('merge_list',merge_list)\n",
    "index_list = [0, 5, 10, 15, 20]\n",
    "max_list = [max(list5), max(list10),max(list20),max(list30),max(list40)]\n",
    "print('max_list',max_list)\n",
    "\n",
    "# 二分查找\n",
    "def binary_search(list,tar):\n",
    "    low = 0\n",
    "    high = len(list)-1\n",
    "    times = 0\n",
    "    if tar> list[high]:\n",
    "        return -1\n",
    "    else:\n",
    "        while low <= high:\n",
    "            times += 1\n",
    "            mid = (low+high)//2\n",
    "            if tar == list[mid]:\n",
    "                return mid\n",
    "            elif tar > list[mid]:\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid - 1\n",
    "        # 由于地板除会导致误差，所以此处需要判断一下\n",
    "        if list[mid]>tar:\n",
    "            return mid\n",
    "        else:\n",
    "            return mid+1\n",
    " \n",
    "# 顺序查找\n",
    "def seq_search(list,tar):\n",
    "    length = len(list)\n",
    "    pos = 0\n",
    "    times = 0 # 统计循环了几次\n",
    "    while pos < length:\n",
    "        times += 1\n",
    "        if list[pos] == tar:\n",
    "            return pos\n",
    "        else:\n",
    "            pos += 1\n",
    "    return -1\n",
    "\n",
    "\n",
    "\n",
    "# 分块查找\n",
    "def block_search(merge_list, index_list, max_list, tar):\n",
    "    # 首先根据二分查找确定区域，也可以用顺序查找\n",
    "    block_num = binary_search(max_list, tar)\n",
    "    print('block_num: ',block_num)\n",
    "    if block_num == -1:\n",
    "        print('二分搜索未找到')\n",
    "        return -1\n",
    "    else:\n",
    "        # 确定在表内，则顺序搜索子列表\n",
    "        search_list = merge_list[index_list[block_num]:index_list[block_num+1]]\n",
    "        print('search_list: ',search_list)\n",
    "        result_index = seq_search(search_list,tar)\n",
    "        if result_index == -1:\n",
    "            print('顺序搜索未找到')\n",
    "            return -1\n",
    "        else:\n",
    "            return index_list[block_num] + result_index\n",
    "\n",
    "print(block_search(merge_list, index_list, max_list, 21))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "分块查找的优点：\n",
    "\n",
    "- 易于修改：在表中插入或删除一个数据时，只需要找到该记录所属得快，就可以在该块进行操作。\n",
    "- 因为块内记录存放是无序的，所以插入/删除比较容易，无需大量修改。  \n",
    "\n",
    "缺点：\n",
    "- 分块查找需要增加辅助存储空间来存储分块查找列表。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 散列查找(Hash查找)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "散列技术(Hash,所以又叫做哈希)既是一种存储方法也是一种查找方法。散列技术的记录之间不存在什么逻辑关系，它只与关键字有关，因此，散列主要是面向查找的存储结构。散列查找法(HashSearch)的思想是通过对元素的关键字值进行某种运算，直接求出元素的地址，即使用关键字到地址的直接转换方法，而不需要反复比较。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " $$ dir = h(key)$$\n",
    " 式中，$key$为关键字；$h$为散列函数(哈希函数)；$dir$为存储位置；"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**相关概念**  \n",
    "- **散列表或哈希表**: 采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表(HashTable);\n",
    "- **Hash函数**：传一个value值给这个函数，这个函数对其进行保存，并把保存的位置key返回给调用方。这是HashTable的构造过程；\n",
    "- **散列(Hash)地址**: 关键字对应的记录存储位置, 也就是以上HashTable中所说的key;\n",
    "- **装填因子**：装填因子 = （哈希表中的记录数） /  （哈希表的长度），装填因子是哈希表装满程度的标记因子。值越大。填入表中的数据元素越多，产生冲突的可能性越大。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Hash函数构造方法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在构造Hash函数时，需要考虑以下几个方面：\n",
    "1. Hash表的长度、key的长度、关键字的分布情况；\n",
    "2. Hash函数计算简单、快速；\n",
    "3. 散列函数能将关键字集合K均匀地分布在地址集{0,1，…，m-1}上，使冲突最小；"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **0. SHA -1** **MD5**  \n",
    "目前应用最为广泛的hash函数是SHA-1和MD5，大多是128位和更长。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **1. 直接定址法:** \n",
    "    - 描述：取关键字的某个线性函数值作为Hash地址  \n",
    "    - 公式：$h(key) = a*key+b; ( a,b为常量 )$\n",
    "    - 适用：需要能够提前知道关键字分布\n",
    "    - 优点：关键字长度与Hash地址长度一致，不存在冲突；\n",
    "    - 缺点：资源占用较多；\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **2. 数字分析法**\n",
    "    - 描述：当关键字的位数很多时，可以通过对关键字的各位进行分析，丢掉分布不均匀的位，以其他位作为Hash地址；\n",
    "    - 公式：假设10位的key，其中3、5、7位比较随机，则$h(key)=h(x_1x_2…x_{10})=x_3x_5x_7$；\n",
    "    - 适用：关键字位数较长；事先知道表中所有关键字每一位数值的分布情况；\n",
    "    - 优点：构造简单，可以直接得出关键字；\n",
    "    - 缺点：它完全依赖于关键字集合；"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **3. 平方取中法**\n",
    "    - 描述：先取关键字的平方，然后根据可使用空间大小，取平方值中间的几位作为关键字；\n",
    "    - 公式：$h(key)=key^2[i_1,i_2,i_3]$\n",
    "    - 适用：位数不大；无需提前了解关键字分布；\n",
    "    - 优点：无需提前获知分布情况，关键字分布较为随机；应用较多；\n",
    "    - 缺点：关键字比较复杂时，计算量大；\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **4. 折叠法**\n",
    "    - 描述：将关键字分成长度相等的几部分(最后一部分位数可以不同)，然后取这几部分的叠加和(去除进位)作为Hash地址；\n",
    "    - 公式：假设将关键字分为3部分：$h(key)=sum(sub_1)+sum(sub_2)+sum(sub_3)$\n",
    "    - 适用：位数较多；无需提前获知关键字分布，但此方法更适用于关键字位数较多，而且关键字中每一位上数字分布大致均匀的情况；\n",
    "    - 优点：计算速度快；\n",
    "    - 缺点：\n",
    "    - 变种： 折叠法中数位折叠又分为移位叠加和边界叠加两种方法\n",
    "        - 移位叠加是将分割后是每一部分的最低位对齐，然后相加；例如：当Hash表长为1000时，关键字key=110108331119891，根据移位叠加：(891)+(119)+(331)+(108)+(110)=1559，去掉最高位后Hash地址为559；\n",
    "        - 边界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加。关键字key=110108331119891，根据移位叠加：(891)+(911)+(331)+(801)+(110)=3044，去掉最高位后Hash地址为044；"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **5. 除留余数法**\n",
    "    - 描述：取某数p除以关键字之后的余数作为Hash地址；\n",
    "    - 公式：$h(key)=mod(key,p) (p ≤ m), m为hash列表长度$ \n",
    "    - 适用：多数情况；\n",
    "    - 优点：计算速度快，方法简单，而且在许多情况下效果较好；\n",
    "    - 缺点：除数p需要慎重选择，不然容易造成冲突，一般情况下可以选p为质数或不包含小于20的质因素的合数（合数指自然数中除了能被1和本身整除外，还能被其他数（0除外）整除的数）；  \n",
    "    理论研究表明，除留余数法的模p取不大于表长且最接近表长m的素数时效果最好，且p最好取1.1n～1.7n之间的一个素数（n为存在的数据元素个数）\n",
    "    - 变种：也可在对关键字进行折叠、平方取中等运算之后取余；"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **6. 伪随机数法**\n",
    "    - 描述：选择一个伪随机函数，选择关键字的随机函数值作为Hash地址；\n",
    "    - 公式：$h(key)=random(key),  其中random为伪随机函数$\n",
    "    - 适用：通常，当关键字长度不等时采用此法构造哈希函数较恰当；\n",
    "    - 优点：\n",
    "    - 缺点："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **7. 相乘取整法**  \n",
    "    - 描述：用关键字key乘上某个常数A(0 < A < 1)，并抽取出key*A的小数部分；然后用m乘以该小数后取整。\n",
    "    - 公式：$h(key)=[mod(key*A)*m]$ \n",
    "    - 适用：\n",
    "    - 优点：该方法最大的优点是m的选取比除余法要求更低。比如，完全可选择它是2的整数次幂。虽然该方法对任何A的值都适用，但对某些值效果会更好。Knuth建议选取 0.61803……。\n",
    "    - 缺点："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **7. 减去法**  \n",
    "    - 描述：减去法是数据的关键字减去一个特定的数值以求得数据存储的位置。\n",
    "    - 公式：$h(key)=key-x$ \n",
    "    - 适用：可以看作直接定址法的一种特例\n",
    "    - 优点：\n",
    "    - 缺点："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **8. 基数转换法**  \n",
    "    - 描述： 将十进制数X看作其他进制，比如十三进制，再按照十三进制数转换成十进制数，提取其中若干为作为X的哈希值。一般取大于原来基数的数作为转换的基数，并且两个基数应该是互素的。\n",
    "    - 公式：$h(key)=$ \n",
    "    - 适用：\n",
    "    - 优点：\n",
    "    - 缺点："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **9. 旋转法**  \n",
    "    - 描述： 将数据的键值在中间进行某种旋转\n",
    "    - 公式：$h(key)=key_{n-3}+...+key_n+...+key_1$ \n",
    "    - 适用：\n",
    "    - 优点：\n",
    "    - 缺点："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **组合使用**\n",
    "    - 上述方法可以自由组合来达到良好的分布效果"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###  冲突解决"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "冲突：关键字不同，但经Hash函数计算后的Hash地址相同。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 开放定址法\n",
    "- 概念：从发生冲突的d单元起,依次探查下一个单元,直到碰到一个空闲单元或探查完所有单元为止。探查时,当达到下标为m-1的表尾单元时(m为列表长度),下一个探查的单元是下标为0的表首单元。\n",
    "- 公式：$h_i(key) = ( h(key) + d_i ) \\% m，(di=1,2,3...,m-1);$ 式中，$h(key)$为哈希函数；$m$为哈希表长度；$d_i$为增量序列,有以下三种常见取值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **1. 线性探查法**\n",
    "    - $d_i = i$\n",
    "    - 优点：只要散列表未填满，总能找到一个不发生冲突的地址。\n",
    "    - 缺点：会产生\"二次聚集\"现象(当表中 i, i+ 1, i+2 位置上已填有记录时，下一个散列地址为i、i+1 、i+2 和i+3 的记录都将填入i+3 的位置，这种在处理冲突过程中发生的两个第一个散列地址不同的记录争夺同一个后继散列地址的现象称作\"二次聚集\"或称作\"堆积\"，即在处理同义词的冲突过程中又添加了非同义词的冲突)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "举例：关键字集合为{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34}，表长为12，$h_i(key) =  key \\% 12$，当存入前5个数字时，不存在冲突，如下表：\n",
    "\n",
    "|下标|0|1|2|3|4|5|6|7|8|9|10|11|\n",
    "|--|--|--|--|--|--|--|--|--|--|--|--|--|\n",
    "|关键字|12|25|||16|||67|56||||\n",
    "\n",
    "计算key=37时，h(37)=37%12=1，与25所在位置产生冲突，所以取$d_i=1$，$h(37)=(37+1)%12=2$,于是将37存入下标为2的位置，其他数值依此类推。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **2. 平方探查法**  \n",
    "    - $d_i = i^2$\n",
    "    - 优点：它是一种较好的处理冲突的方法，可以较好避免堆积现象\n",
    "    - 缺点：不能探查到散列表上所有单元；"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **3. 伪随机探查法**\n",
    "    - $d_i =random(i)$\n",
    "    - 优点：可以避免\"二次聚集\"现象\n",
    "    - 缺点：：不能保证一定找到不发生冲突的地址，不保证能探查到散列表上所有单元"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **双散列函数探查法**\n",
    "    - 概念：该方法使用两个散列函数h1和h2，其中h1和前面的h(K)一样，以关键字为自变量，产生一个0～m-1之间的数作散列地址;h2也以关键字为自变量，产生一个1～m-1之间的、并和m互素的数作散列地址。\n",
    "    - 公式： $d_i =i*h_2(key)，对任意的key，h2(key) != 0$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **再散列函数探查法**\n",
    "    - 概念：当散列表元素太多（即装填因子太大）时，查找效率会下降；当装填因子过大时，解决方法是加倍扩大散列表，这个过程叫做“再散列（Rehashing）”，相当于重新设计列表，修改Hash函数；\n",
    "    - 公式："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 链地址法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 概念：将全部具有同样哈希地址的而不同keyword的数据元素连接到同一个单链表中，用于链接同义词表，又叫拉链法。\n",
    "- 优点：\n",
    "    - 1、拉链法**处理冲突较为简单，且无堆积现象**，即非同义词绝不会发生冲突，因此平均查找长度较短；\n",
    "    - 2、拉链法中的链表上各节点是动态申请的，因此**更适用于造表前无法确定表长的情况**；\n",
    "    - 3、**节省空间**，开放定址法为降低冲突，要求装填因子α较小，故当结点规模较大时会浪费非常多空间；而拉链法中可取α≥1，且结点较大时，拉链法中添加的指针域可忽略不计，因此节省空间； \n",
    "    - 4、在用拉链法构造的散列表中，**删除结点的操作易于实现**，仅仅要简单地删去链表上对应的结点就可以。（而对开放地址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填入散列表的同义词结点的查找路径，这是由于各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。）\n",
    "- 缺点：查找时需要遍历单链表产生性能损耗"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![]()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "关于同义词表的建立，有两种方法。\n",
    "- 一种方法是在散列表的基本存储区域外开辟一个新的区域用于存储同义词表，这种方法称为“分离的同义词子表法”，或称“独立链表地址法”，这个分离的同义词子表所在的区域称为“溢出区”。\n",
    "- 另一种方法是不建立溢出区，而是将同义词子表存储在散列表所在的基本存储区域里，例如，可以再基本存储区域里从后向前探测空闲表项，找到后就将其链接到同义词子表中，这个方法称为“结合的同义词子表法”，或称为“公共链表地址法”。   \n",
    "\n",
    "对比：\n",
    "- 独立链表地址法是查找效率最好的解决冲突的方法，速度要快于开放地址法，因为独立链表地址法在进行散列查找时仅需搜索同义词表。开放地址法要求表长时固定的，而地理链表法中的表项则是动态分配的，其表长仅受内存空间的限制。链表法的主要缺点是需要为每个表项（包括分离的同义子表的每个节点）设立一个指针域。**总之，独立链表地址法的动态结构使它成为散列法中解决冲突的首选方法。**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 公共溢出区法\n",
    "- 概念：为所有冲突的关键字建立一个公共的溢出区来存放，在查找时，对给定值通过散列函数计算出散列地址后，先与基本表的相应位置进行比对，如果相等，则查找成功，如果不相等，则到溢出表去进行顺序查找；\n",
    "- 优点：如果对于基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 性能分析"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "散列表查找性能分析，成功平均查找长度（ASLs），不成功平均查找长度（ASLu）,查找次数＝冲突次数＋1；\n",
    "- ASLs：查找表中关键词的平均查找比较次数，ASLs＝元素的查找次数总和／元素总个数\n",
    "- ASLu：不在散列表中的关键词的平均查找次数（不成功），"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![]()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "参考文档：  \n",
    "- 哈希函数的构造方法：https://blog.csdn.net/u011037053/article/details/82080023\n",
    "- 哈希函数的构造方法：https://www.cnblogs.com/gj-Acit/archive/2013/05/06/3062628.html\n",
    "- P4 哈希函数的常用构造方法：https://www.cnblogs.com/east7/p/12607877.html\n",
    "- 查找-散列表查找(哈希表)：https://www.jianshu.com/p/191034693a1d\n",
    "- 散列查找法(HashSearch)：https://www.cnblogs.com/lygzcom/p/12843325.html\n",
    "- 散列查找 ——哈希查找：https://blog.csdn.net/qq_40893056/article/details/80054198\n",
    "- 哈希表——线性探測法、链地址法、查找成功、查找不成功的平均长度: https://www.cnblogs.com/gavanwanggw/p/7307596.html\n",
    "- 数据结构—— 处理散列冲突的四种方法【开放定址法-再散列函数法-链地址法-公共溢出区法】：https://blog.csdn.net/liu17234050/article/details/104271343#%E5%9B%9B%EF%BC%9A%C2%A0%E5%85%AC%E5%85%B1%E6%BA%A2%E5%87%BA%E5%8C%BA%E6%B3%95"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 树表查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python不需要数、图的数据类型，所以暂时不进行学习。大概看一下参考文献，学习其基本原理，不造轮子了。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 参考文献：\n",
    "树表的查找：https://blog.csdn.net/kong_xz/article/details/79558694"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  },
  "toc-autonumbering": true
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
